Sliding Window Aggregation
Operations
半群の列 $ (a_0, a_1, \dots, a_{n - 1}) を扱う．
空間計算量$ \Theta(n)
$ \mathtt{new}()
空の状態でデータ構造を作成する
時間計算量$ \Theta(1)
$ \mathtt{fold\_all}()
$ a_0 \cdot a_{1} \cdot \dots \cdot a_{n-1}を計算する
時間計算量$ \Theta(1)
$ \mathtt{push}(x)
$ xを末尾に追加する
時間計算量$ \Theta(1)
$ \mathtt{pop}()
$ a_0を削除する
時間計算量$ \Theta(1) \ \rm amortized
Summary
Queue を$ 2つの Stack でシミュレートする技法を用いる
それぞれの Stack は要素の他に、最初の要素からその位置までの累積和も管理する
https://gyazo.com/c00a9408b49af480dd37ba3b879847ba
先頭側の Stack 全体と末尾側の Stack 全体の fold 結果はわかっているので，それらを結合すれば$ \mathtt{fold\_all}に答えられる
$ \mathtt{pop}
https://gyazo.com/9424f946b39c798777606931dc13f029
先頭側の Stack が空でないとき，単に先頭側の Stack を pop する
https://gyazo.com/efd5cdd7aeb108c7217203c29c050573
先頭側の Stack が空になった際に末尾側の Stack の全要素を反転して先頭にする
この操作には$ \Theta(n)かかるが，$ 1つの要素が Stack に $ \mathtt{push}, \mathtt{pop}される回数を考えると償却定数時間になることが言える．
References
Notes
同様に$ 2つの Stack を用いて全体の和が計算可能な Deque も作成可能である
min の成す半群については Deque を用いた別のアルゴリズムが知られている (スライド最小値)
Implementations
Problems